// NC28.最小覆盖子串
// https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac  [较难]
// 滑窗
//给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。
//输入 "XDOYEZODEYXNZ","XYZ"
//返回值 "YXNZ"
#include <algorithm>
#include <iostream>
#include <map>
#include <memory>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
 public:
  string minWindow_moveWin(string S, string T) {
    // 表示窗口左右位置的指针
    // start 表示最后结果字符串开始位置
    // minlen表示最后字符串长度，二者可以表示一个字符串
    // need的存放字符串T的所有字符统计
    // window 存放现有的窗口中出现在need中的字符统计
    int left = 0, right = 0;
    int start = 0, minLen = INT_MAX;
    map<char, int> need;
    map<char, int> window;

    for (auto i : T) need[i]++;
    int match = 0;
    // window与need的匹配度
    while (right < S.length()) {
      char c1 = S[right];
      if (need.count(c1)) {
        window[c1]++;
        if (window[c1] == need[c1]) match++;
      }
      right++;
      // 当匹配度等于need.size(),说明这段区间可以作为候选结果，更新ret
      while (match == need.size()) {
        if (right - left < minLen) {
          minLen = right - left;
          start = left;
        }
        char c2 = S[left];
        if (need.count(c2)) {
          window[c2]--;
          if (window[c2] < need[c2]) match--;
        }
        left++;
      }
    }
    return minLen == INT_MAX ? "" : S.substr(start, minLen);
  }

  string minWindow(string S, string T) { return ""; }
};

int main_nc28() {
  multimap<int, int> stNumber;
  stNumber.insert({23, 5});
  for (auto it : stNumber) {
    printf("%d.", it);
  }
  printf("\n");
  printf("size=%d.\n", stNumber.size());
  stNumber.insert({32, 6});
  for (auto it : stNumber) {
    printf("%d.", it);
  }
  printf("\n");
  printf("size=%d.\n", stNumber.size());
  stNumber.insert({32, 4});
  for (auto it : stNumber) {
    printf("%d.", it);
  }
  printf("\n");
  printf("size=%d.\n", stNumber.size());
  stNumber.erase(32);
  for (auto it : stNumber) {
    printf("%d.", it);
  }
  printf("\n");
  printf("size=%d.\n", stNumber.size());
  stNumber.erase(32);
  for (auto it : stNumber) {
    printf("%d.", it);
  }
  printf("\n");
  printf("size=%d.\n", stNumber.size());
  stNumber.erase(32);
  for (auto it : stNumber) {
    printf("%d.", it);
  }
  printf("\n");
  printf("size=%d.\n", stNumber.size());
  stNumber.erase(32);
  for (auto it : stNumber) {
    printf("%d.", it);
  }
  printf("\n");
  printf("size=%d.\n", stNumber.size());

  return 0;

  Solution sol;
  string str = sol.minWindow("XDOYEZODEYXNZ", "XYZ");
  printf("%s\n", str.c_str());
  return 0;
}
